1.Main page

SNAP System

Stanford Network Analysis Platform (SNAP) 是一种通用的，对于大的网络的分析和操作的高性能系统。图形由节点和图形节点之间的有向/无向/ 多边组成。网络是具有网络节点和/或边缘上的数据的图形。

核心SNAP库以C ++编写，并针对最大性能和紧凑图表示进行了优化。它容易扩展到具有数亿个节点和数十亿边缘的大规模网络。它有效地操纵大图，计算结构属性，生成规则和随机图，并支持节点和边缘上的属性。除了对大型图形的可扩展性外，SNAP的另外一个优点是图形或网络中的节点，边缘和属性可以在计算过程中动态更改。

SNAP最初由Jure Leskovec在博士研究生课程中开发。第一个版本于2009年11月提供.SNAP使用在Jozef Stefan研究所开发的通用STL（标准模板库）类库GLib。SNAP和GLib正在积极开发并用于许多学术和工业项目。

2.Download SNAP

Current SNAP Release: SNAP 4.0 (2017年7月27日)

A public development SNAP repository is available at GitHub:snap-stanford/snap

其他有用的第三方包：

  • Gnuplot，绘图和绘图包，用于绘制网络的结构属性（如度数分布）;
  • Graphviz是绘图和可视化小图所需的绘图包;
  • NodeXL，一个将网络分析和SNAP集成到Microsoft Office和Excel中的图形前端。它允许没有编程技能的用户使用SNAP。

3.SNAP User Documentation

(1) Quick Introduction

Graph and Network Types

Graph types in SNAP:

  • TUNGraph: 无向图（无序对节点之间的单边）
  • TNGraph: 有向图（有序节点对之间的单向边）
  • TNEGraph: 有向多图（一对节点之间的多个有向边）

Network types in SNAP:

  • TNodeNet: 像TNGraph，但是对于每个节点都有TNodeData对象
  • TNodeEDatNet: 像TNGraph，但是每个节点上都有TNodeData，每个边上
    都有TEdgeData
  • TNodeEdgeNet: 像TNEGraph，但是使用TNodeData每个节点和每个边上的
  • TNEANet: 像TNEGraph，但节点和边上具有属性。这些属性是动态的，因为它们可以在运行时定义
  • TBigNet: TNodeNet的内存高效实现，可以避免内存碎片，并处理数十亿个边，并提供足够的RAM

Graph Creation

创建一个有向图：

1
2
3
4
5
6
7
8
// create a graph
PNGraph Graph = TNGraph::New();
Graph->AddNode(1);
Graph->AddNode(5);
Graph->AddNode(32);
Graph->AddEdge(1, 5);
Graph->AddEdge(5, 1);
Graph->AddEdge(5, 32);

节点ID没有限制为从0开始的连续整数。
SNAP使用智能指针（TPt），因此不需要显式释放（删除）图形对象。当他们不再需要时，他们会自我毁灭。类名中的前缀P表示指针，而T表示类型。

网络的创建方式与图形相同。

Iterators(迭代器)

  • iterator usage of directed/undirected data types

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // create a directed random graph on 100 nodes and 1k edges
    PNGraph Graph = TSnap::GenRndGnm<PNGraph>(100, 1000);
    // traverse the nodes
    for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
        printf("node id %d with out-degree %d and in-degree %d\n",
            NI.GetId(), NI.GetOutDeg(), NI.GetInDeg());
    }
    // traverse the edges
    for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
        printf("edge (%d, %d)\n", EI.GetSrcNId(), EI.GetDstNId());
    }
    // we can traverse the edges also like this
    for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
        for (int e = 0; e < NI.GetOutDeg(); e++) {
            printf("edge (%d %d)\n", NI.GetId(), NI.GetOutNId(e));
        }
    }

  • In general graph/network data types use the following functions to return various iterators.

    1
    2
    3
    4
    5
    6
    7
    BegNI(): iterator to first node
    EndNI(): iterator to one past last node
    GetNI(u): iterator to node with id u
    BegEI(): iterator to first edge
    EndEI(): iterator to one past last edge
    GetEI(u,v): iterator to edge (u,v)
    GetEI(e): iterator to edge with id e (only for multigraphs)

  • 一般来说，节点迭代器提供以下功能：

    1
    2
    3
    4
    5
    6
    7
    8
    GetId() : return node id
    GetOutDeg() : return out - degree of a node
    GetInDeg() : return in - degree of a node
    GetOutNId(e) : return node id of the endpoint of e - th out - edge
    GetInNId(e) : return node id of the endpoint of e - th in - edge
    IsOutNId(int NId) : do we point to node id n
    IsInNId(n) : does node id n point to us
    IsNbhNId(n) : is node n our neighbor

  • 此外，网络上的迭代器还可以轻松访问数据：

    1
    2
    3
    4
    5
    GetDat(): return data type TNodeData associated with the node
    GetOutNDat(e): return data associated with node at endpoint of e-th out-edge
    GetInNDat(e): return data associated with node at endpoint of e-th in-edge
    GetOutEDat(e): return data associated with e-th out-edge
    GetInEDat(e): return data associated with e-th in-edge

输入/输出

使用SNAP可以轻松地以各种格式保存和加载网络。内部SNAP以紧凑的二进制格式保存网络，但也可以使用各种其他文本和XML格式加载和保存网络的功能（参见gio.h）。
// generate a network using Forest Fire model
PNGraph G = TSnap::GenForestFire(1000, 0.35, 0.35);
// save and load binary
{ TFOut FOut(“test.graph”); G->Save(FOut); }
{ TFIn FIn(“test.graph”); PNGraph G2 = TNGraph::Load(FIn); }
// save and load from a text file
TSnap::SaveEdgeList(G2, “test.txt”, “Save as tab-separated list of edges”);
PNGraph G3 = TSnap::LoadEdgeList(“test.txt”, 0, 1);

操纵图和网络

SNAP提供丰富的功能来有效地操纵图形和网络。函数实现为命名空间TSnap的一部分。所有功能都支持任何图形/网络类型。

1
2
3
4
5
6
7
8
9
10
11
12
// generate a network using Forest Fire model
PNGraph G = TSnap::GenForestFire(1000, 0.35, 0.35);
// convert to undirected graph TUNGraph
PUNGraph UG = TSnap::ConvertGraph<PUNGraph>(G);
// get largest weakly connected component of G
PNGraph WccG = TSnap::GetMxWcc(G);
// get a subgraph induced on nodes {0,1,2,3,4,5}
PNGraph SubG = TSnap::GetSubGraph(G, TIntV::GetV(0,1,2,3,4));
// get 3-core of G
PNGraph Core3 = TSnap::GetKCore(G, 3);
// delete nodes of degree 10
TSnap::DelDegKNodes(G, 10);

计算结构属性

SNAP提供丰富的功能来有效地计算网络的结构属性。函数实现为命名空间TSnap的一部分。所有功能都支持任何图形/网络类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// generate a Preferential Attachment graph on 1000 nodes and node out degree of 3
PUNGraph G = TSnap::GenPrefAttach(1000, 3);
// get distribution of connected components (component size, count)
TVec<TPair<TInt, TInt> > CntV; // vector of pairs of integers (size, count)
TSnap::GetWccSzCnt(G, CntV);
// get degree distribution pairs (degree, count)
TSnap::GetOutDegCnt(G, CntV);
// get first eigenvector of graph adjacency matrix
TFltV EigV; // vector of floats
TSnap::GetEigVec(G, EigV);
// get diameter of G
TSnap::GetBfsFullDiam(G);
// count the number of triads in G, get the clustering coefficient of G
TSnap::GetTriads(G);
TSnap::GetClustCf(G);

(2) Installation and Compilation

Prerequisites先决条件

SNAP在Windows下使用Visual Studio或Cygwin与GCC，Mac OS X，Linux和其他具有GCC的Unix变体一起工作。确保系统上安装了C ++编译器。

SNAP主要是独立的，只需要外部包装才能绘制和可视化。需要在系统上安装以下软件包以支持SNAP中的绘图和可视化：

  • Gnuplot用于绘制网络结构性质（例如度数分布）;
  • Graphviz用于绘制和可视化小图。

设置系统PATH变量，以便Gnuplot和Graphviz可用，或将可执行文件放在工作目录中。

SNAP Components

SNAP分发包包含以下组件：

  • snap-core：核心SNAP图库;
  • snap-adv：高级SNAP组件，不在核心，而是由示例使用;
  • snap-exp：实验SNAP组件，仍在开发中;
  • 示例：演示SNAP功能的小型示例应用程序;
  • 教程：简单的程序，演示使用各种类;
  • glib-core：实现基本数据结构的STL类库，如向量（TVec），散列表（THash）和字符串（TStr），提供序列化等;
  • 测试：各类单元测试;
  • doxygen： SNAP参考手册。

Installation

要安装SNAP，下载最新的SNAP发行安装包，并解压缩。

为了绘制网络的结构属性（例如，度分布），SNAP期望在系统路径中找到Gnuplot。类似于绘图和可视化小图SNAP使用Graphviz。如果需要，请安装这些软件包，并确保系统PATH变量指向其可执行文件或将可执行文件放在工作目录中。

Compilation of SNAP Programs（SNAP程序的编译）

SNAP在Mac OS X，Linux和Windows上使用Cygwin

确保在系统上安装了带有C++编译器的GCC包。

在主SNAP目录中运行“make all”。这将编译核心SNAP库和所有应用示例。

对于其他平台，请修改主SNAP目录中的Makefile.config。

SNAP在Windows与Visual Studio

确保您的系统上安装了Visual Studio。启动Visual Studio并在examples目录中打开解决方案文件SnapExamples 。

配置Visual Studio与SNAP一起使用，需要将字符集设置为多字节，并指定SNAP包含目录的位置。

要将字符集设置为多字节，请右键单击项目，转到属性 - > 配置属性 - > 常规 - > 项目默认值 - > 字符集 - > 选择“使用多字节字符集“。

要指定SNAP包含目录的位置，请转到选项 - > 首选项 - > C ++目录 - > 包含目录，并将系统上的路径添加到SNAP文件夹glib-core，snap-core和snap-adv。

请注意，您的Visual Studio版本的设置可能与上面使用的位置略有不同，因此要找到它们的导航步骤需要适当调整。

一旦配置Visual Studio，构建您的解决方案，编译核心SNAP库的所有示例。

Execution of SNAP Programs(SNAP程序的执行)

代码如上所示编译后，就可以执行。所述graphgen申请在此用作一个例子。

要运行graphgen示例，请打开命令行应用程序并执行以下命令：

cd examples/graphgen
./graphgen -g:w -n:1000 -k:4 -p:0.1 -o:smallworld.txt

该命令生成Watts-Strogatz小世界图，其中每个节点连接到k = 4个最接近的节点，并且重新布线概率为p = 0.1。

##(3) Package Description

SNAP目录结构

SNAP包包含以下目录：

  • snap-core：核心SNAP图库;
  • snap-adv：高级SNAP组件，不在核心，而是由示例使用;
  • snap-exp：实验SNAP组件，仍在开发中;
  • examples：演示SNAP功能的小型示例应用程序;
  • tutorials：简单的程序，演示使用各种类;
  • glib-core：实现基本数据结构的STL类库，如向量（TVec），散列表（THash）和字符串（TStr），提供序列化等;
  • test：各类单元测试;
  • doxygen： SNAP参考手册。

示例应用程序

agmfit：通过将关联图模型（AGM）通过最大似然估计拟合到给定网络来检测来自给定网络的网络社区。
agmgen：实现关联图模型（AGM）。AGM从节点的社区归属生成一个逼真的图。
bigclam：将社区检测问题制定为非负矩阵分解，并发现节点的社区隶属因子。
cascadegen：标识事件列表中的级联。
cascades: 模拟网络上的SI（敏感感染）模型，并计算级联的结构属性。
centrality: 计算图形的节点中心性度量：亲密度，特征，度数，中间性，页面级别，中心和权限。
cesna：实现基于边缘结构和节点属性（CESNA）的社区的具有节点属性的网络的大规模重叠社区检测方法。
circles：实现识别用户社交圈的方法。
cliques: 基于Clique Percolation方法，找出网络中重叠密集的节点组。
coda：通过定向关联（CoDA）实现基于社区的大规模重叠社区检测方法，该方法处理有向和无向网络。该方法能够找到成员节点形成二维连通性结构的2模式社区。
community: 实施网络社区检测算法：Girvan-Newman，Clauset-Newman-Moore和Infomap。
concomp：计算弱，强和双连接的组件，关节点和图形的桥边。
flows：计算网络中的最大网络流量。
forestfire: 使用森林火灾模型生成图。
graphgen：使用许多SNAP图生成器之一生成无向图。
graphhash：演示使用TGHash图表哈希表，用于计算小子图或信息级联的频率。
infopath：实现级联数据动态网络推理的随机算法，参见在线媒体信息通路的结构与动力学
kcores：计算网络的k-核心分解，并绘制图形k核心中的节点数作为k的函数。
knnjaccardsim：基于Jaccard相似性构建K最近邻的图。
kronem：使用EM算法估计Kronecker图参数矩阵。
kronfit：估计Kronecker图参数矩阵。
krongen: 生成克罗内克图。
localmotifcluster：在目标种子节点周围找到具有低基序电导的节点集合。
lshtest：实现局部敏感散列。
magfit：估计乘数属性图（MAG）模型参数。
maggen：生成乘法属性图（MAG）。
mkdatasets：演示如何以各种网络格式加载不同类型的网络，以及如何计算网络的各种统计信息。
motifcluster: 实现基于图案的聚类的光谱方法。
motifs: 计算网络中K个节点上每个可能的子图的发生次数。
ncpplot：绘制网络社区配置文件（NCP）。
netevol：计算不断发展的网络的属性，如直径演化，密度函数法，度数分布等。
netinf：从级联数据实现网络推理的netinf算法，请参阅推理扩散和影响网络
netstat：计算静态网络的结构属性，如度分布，跳线图，聚类系数，连通分量大小分布，图形邻接矩阵的谱特性等。
node2vec：计算节点在d维空间中的嵌入。
randwalk：计算节点对之间的个性化PageRank。
rolx：实现用于分析图中结构角色的rolx算法。
temporalmotifs: 计算时间网络中的所有三节点，三边缘时间图案。
testgraph: 演示一些基本的SNAP功能。
zygote: 演示如何使用SNAP与Zygote库，这显着加快了需要多次处理相同大图的计算。

核心SNAP库的功能

在发行包中的各种文件中实现的SNAP功能的简要说明：

  • snap-core
  • snap-adv
  • snap-exp

(4)Tutorial

用于社交媒体建模，分析和优化的技术基于对大规模网络的研究，其中网络可以包含数亿个节点和数十亿个边缘。网络分析工具不仅要提供广泛的功能，还要提供处理这些大型网络的高性能。

本教程将介绍斯坦福网络分析平台（SNAP），这是一个通用的高性能系统，用于分析和操纵大型网络。SNAP被广泛用于网络和社交媒体的研究。它由开放源代码软件组成，它提供了丰富的功能来执行网络分析，以及一个受欢迎的公开的现实世界网络数据集库。SNAP软件API可用于Python和C ++。

本教程将涵盖SNAP的所有方面，包括SNAP API和SNAP数据集。本教程针对具有一些编程背景的入门级受众，因此Python API将比C ++ API更详细地讨论。本教程将包括一个动手组件，参与者将有机会在其计算机上使用SNAP。

(5)User Reference Manual

SNAP库4.0，用户参考文档

本文档提供SNAP API的参考文档。该文档还包括对源代码的完整参考。要开始，请浏览左列中的类或文件部分，或在右上方的搜索框中搜索特定项目。

本文档有两个版本，用户参考和开发人员参考。开发人员参考文献更广泛。它包括类的继承和协作图，函数的调用和调用图。这些图和图表不包括在用户参考文档中。

关于Snap

斯坦福网络分析平台（SNAP）是一种用于分析和操纵大型网络的通用高性能系统。图形由节点和图形节点之间的有向/无向/多边组成。网络是具有网络节点和/或边缘上的数据的图形。

核心SNAP库以C ++编写，并针对最大性能和紧凑图表示进行了优化。它容易扩展到具有数亿个节点和数十亿边缘的大规模网络。它有效地操纵大图，计算结构属性，生成规则和随机图，并支持节点和边缘上的属性。除了对大型图形的可扩展性外，SNAP的另外一个优点是图形或网络中的节点，边缘和属性可以在计算过程中动态更改。

SNAP在Windows上使用Visual Studio或Cygwin与GCC，Mac OS X，Linux和其他具有GCC安装的Unix版本。SNAP在很大程度上是独立的，对其他软件包的依赖性要求最低。

SNAP使用在Jozef Stefan研究所开发的通用STL（标准模板库）类库。SNAP和GLib正在积极开发并用于许多学术和工业项目。

核心SNAP和GLib库的完整源代码可在BSD许可证下获得。在http://snap.stanford.edu下载软件包。

Support

对于常见问题未涵盖的问题或有关SNAP安装，使用和开发的讨论，请使用SNAP用户邮件列表。要发布到组，请发送您的消息，以在googlegroups dot com上进行讨论。

Developer Resources

GitHub SNAP存储库

GitHub snap-stanford/snap可以使用公共开发库。

开发人员参考手册

对SNAP中所有类和方法的广泛交叉引用。

SNAP C ++编程指南

核心SNAP库的贡献者的编程指南